package org.concepts.algorithm.datastructure;

public class TreeUtils {

  /**
   * Traversal of a node must be done in the specified order.
   * <p/>
   * 
   * <ol>
   * <li>PREORDER: Visit all the nodes first and then the left child followed by
   * the right child</li>
   * <li>INORDER: Visit the left child, followed by the root and then the right
   * child.</li>
   * <li>POSTORDER: Visit left child, followed by right and finally the root.</li>
   * </ol>
   * 
   * @author vvvv
   * 
   */
  public enum Traversal {
    PREORDER, INORDER, POSTORDER
  };

  /**
   * Does a breadth first traversal of the node.
   * 
   * @param <V>
   * @param tree
   */
  public static <V> void breadthFirstTraversal(Tree<V> tree) {
    Node<V> rootNode = tree.getRootNode();
    if (rootNode == null) {
      return;
    }
    breadthFirstTraversal(rootNode);
  }

  public static <V> void breadthFirstTraversal(Node<V> node) {
    for (Node<V> childNode : node.getChildren()) {
      System.out.println("Node: " + childNode);
    }
    for (Node<V> childNode : node.getChildren()) {
      breadthFirstTraversal(childNode);
    }
  }

  public static <V> void depthFirstTraversal(Node<V> node, Traversal traversal) {
    switch (traversal) {
    case INORDER:
      inOrderDFSTraversal(node, traversal);
      break;
    case POSTORDER:
      postOrderDFSTraversal(node, traversal);
      break;
    case PREORDER:
      preOrderDFSTraversal(node, traversal);
      break;
    }

  }

  private static <V> void postOrderDFSTraversal(Node<V> node,
      Traversal traversal) {
    for (Node<V> childNode : node.getChildren()) {
      // traverse children left to right before node
      depthFirstTraversal(childNode, traversal);
    }
    System.out.println("Node: " + node);
  }

  private static <V> void preOrderDFSTraversal(Node<V> node, Traversal traversal) {
    System.out.println("Node: " + node);
    for (Node<V> childNode : node.getChildren()) {
      // traverse children left to right after node
      depthFirstTraversal(childNode, traversal);
    }
  }

  private static <V> void inOrderDFSTraversal(Node<V> node, Traversal traversal) {
    if (node.getChildren().size() > 0) {
      depthFirstTraversal(node.getChildren().get(0), traversal);
    }

    System.out.println("Node: " + node);

    int ctr = 0;
    for (Node<V> childNode : node.getChildren()) {
      if (ctr++ == 0) {
        continue;
      }
      depthFirstTraversal(childNode, traversal);
    }
  }

}
